/**
 * @program: LeetCode
 * @description: LeetCode : 221. 最大正方形
 * @author: WXY
 * @create: 2023-01-09 19:58
 * @Version 1.0
 **/
public class Num221_maximalSquare {
    //当我们判断以某个点为正方形右下角时最大的正方形时，
    // 那它的上方，左方和左上方三个点也一定是某个正方形的右下角，否则该点为右下角的正方形最大就是它自己了。这是定性的判断，
    // 那具体的最大正方形边长呢？
    // 我们知道，该点为右下角的正方形的最大边长，最多比它的上方，左方和左上方为右下角的正方形的边长多1，
    // 最好的情况是是它的上方，左方和左上方为右下角的正方形的大小都一样的，这样加上该点就可以构成一个更大的正方形。
    // 但如果它的上方，左方和左上方为右下角的正方形的大小不一样，合起来就会缺了某个角落，
    // 这时候只能取那三个正方形中最小的正方形的边长加1了。
    // 假设dpi表示以i,j为右下角的正方形的最大边长，
    // 则有 dp[i][j] = min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) + 1
    // 当然，如果这个点在原矩阵中本身就是0的话，那dp[i]肯定就是0了。
    public static int maximalSquare(char[][] matrix) {
        int m = matrix.length; // 行
        int n = matrix[0].length;//列
        int[][] dp = new int[m + 1][n + 1];
        int max = 0;
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (matrix[i - 1][j - 1] == '1') {
                    dp[i][j] = Math.min(dp[i - 1][j - 1], Math.min(dp[i - 1][j], dp[i][j - 1])) + 1;
                    max = Math.max(max, dp[i][j]);
                }
            }
        }
        return max * max;
    }

    public static int maximalSquare1(String[][] matrix) {
        int m = matrix.length; // 行
        int n = matrix[0].length;//列
        int[][] left = new int[m][n];
        int[][] up = new int[m][n];
        int[][] dp = new int[m][n];
        int max = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == "1") {
                    left[i][j] = j > 0 ? left[i][j - 1] + 1 : 1;
                }
            }
        }
        int curpre = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == "1") {
                    up[i][j] = i > 0 ? up[i - 1][j] + 1 : 1;
                }
            }
        }
        curpre = 1;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                int width = left[i][j];
                int high = up[i][j];
                int cur = Math.min(width, high);
                dp[i][j] = cur * cur;
                if (dp[i][j] > 1) {
                    dp[i][j] = dp[i - 1][j - 1] == 0 ? 1 : (dp[i - 1][j - 1] >= (cur - 1) * (cur - 1) ? cur * cur : (int) Math.pow((Math.sqrt(dp[i - 1][j - 1]) + 1), 2));
                }
                max = Math.max(dp[i][j], max);
            }
        }
        curpre = 1;
        return max;
    }

    public static void main(String[] args) {
        String[][] arr = {{"0", "0", "0", "1"}, {"1", "1", "0", "1"}, {"1", "1", "1", "1"}, {"0", "1", "1", "1"}, {"0", "1", "1", "1"}};
        int i = maximalSquare1(arr);
        System.out.println(i);
    }
}
